package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yinlei
 * @date 2018/6/27
 * @since 1.0.0
 */
public class N022GenerateParentheses {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }


    static public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        
        handleResult(list, "", n, 0);
        return list;
    }

    private static void handleResult(List<String> list, String s, int m, int n) {

        if (m == 0 && n == 0) {
            list.add(s);
            return;
        }

        if (m > 0) {
            handleResult(list, s + "(", m - 1, n + 1);
        }
        if (n > 0) {
            handleResult(list, s + ")", m, n - 1);
        }
    }

//    static public List<String> generateParenthesis(int n) {
//        List<String> list = new ArrayList<>();
//        for (int i = 0;i < n; i++) {
//            StringBuffer sb = new StringBuffer(n * 2);
//
//            for (int j = 0; j < i; j++) {
//                sb.append("()");
//            }
//
//            StringBuffer last = new StringBuffer();
//
//            for (int j = i; j < n; j++) {
//                sb.append("(");
//                last.append(")");
//            }
//
//            sb.append(last.toString());
//            list.add(sb.toString());
//        }
//
//        return list;
//    }
}
